package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/13 14:47
 * @description：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/
 */
public class 保持城市天际线 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.maxIncreaseKeepingSkyline(new int[][]{{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0}}));
    }

    class Solution {
        public int maxIncreaseKeepingSkyline(int[][] grid) {
            int n = grid.length;
            int[] maxRow = new int[n];
            int[] maxCol = new int[n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    maxRow[i] = Math.max(maxRow[i], grid[i][j]);
                    maxCol[j] = Math.max(maxCol[j], grid[i][j]);
                }
            }
            int max_incr = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    max_incr += Math.min(maxRow[i], maxCol[j]) - grid[i][j];
                }
            }
            return max_incr;
        }
    }

    /*
    class Solution {
        public int maxIncreaseKeepingSkyline(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < m; i++) {
                int max = 0;
                for (int j = 0; j < n; j++) {
                    max = Math.max(max, grid[i][j]);
                    map.put(m + j, Math.max(map.getOrDefault(m + j, 0), grid[i][j]));
                }
                map.put(i , max);
            }
            int max_incr = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int max = Math.min(map.get(i), map.get(m + j));
                    max_incr += max - grid[i][j];
                }
            }
            return max_incr;
        }
    }
     */
}
